/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/clone-graph
   @Language: C++
   @Datetime: 16-02-09 05:44
   */

/**
 * Definition for undirected graph.
 * struct UndirectedGraphNode {
 *     int label;
 *     vector<UndirectedGraphNode *> neighbors;
 *     UndirectedGraphNode(int x) : label(x) {};
 * };
 */

// Method 1, DFS, Time 79ms
class Solution {
	UndirectedGraphNode *cloneCore(UndirectedGraphNode *node
			,unordered_map<UndirectedGraphNode*,UndirectedGraphNode*> &vist){
		if (node==NULL) return NULL;
		if (vist.find(node)!=vist.end()) return vist[node];
		UndirectedGraphNode *g = new UndirectedGraphNode(node->label);
		vist[node]=g;
		for(const auto &n : node->neighbors)
			g->neighbors.push_back(cloneCore(n,vist));
		return g;
	}

public:
	/**
	 * @param node: A undirected graph node
	 * @return: A undirected graph node
	 * Tip: Using hashmap record visited nodes
	 */
	UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
		// write your code here
		unordered_map<UndirectedGraphNode*,UndirectedGraphNode*> vist;
		return cloneCore(node,vist);
	}
};

// Method 2, BFS, Time 79ms
class Solution {
public:
	/**
	 * @param node: A undirected graph node
	 * @return: A undirected graph node
	 * Tip: Using hashmap record visited nodes
	 */
	UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
		// write your code here
		if (node==NULL) return NULL;
		unordered_map<UndirectedGraphNode*,UndirectedGraphNode*> vist;
		queue<UndirectedGraphNode*> que;
		vist[node] = new UndirectedGraphNode(node->label);
		for(que.push(node); que.size(); que.pop()){
			UndirectedGraphNode *q = que.front();
			for(const auto &n : q->neighbors){
				if (vist.find(n)==vist.end()){
					vist[n] = new UndirectedGraphNode (n->label);
					que.push(n);
				}
				vist[q]->neighbors.push_back(vist[n]);
			}
		}
		return vist[node];
	}
};
